package com.lry.basic.algorithm.graph;


//二分图检测,多个连通分量只要一个连通分量不是二分图整体就不是二分图
public class BiPartitionDetection {

    private UndirectedGraph graph;
    private boolean[] visited;
    private int[] colors;
    private boolean biPart = true;

    public BiPartitionDetection(UndirectedGraph graph){
        this.graph = graph;
        visited = new boolean[graph.vertexNum()];
        colors = new int[graph.vertexNum()];
        for(int i=0;i<colors.length;i++){
            colors[i] = -1;
        }

        for(int v=0;v<graph.vertexNum();v++){
            if(!visited[v]){
                if(!dfs(v,0)){
                    biPart = false;
                    break;
                }
            }
        }
    }

    private boolean dfs(int v,int color){
        visited[v] = true;
        colors[v] = color;
        for(int w:graph.adj(v)) {
            if(!visited[w]){
                if(!dfs(w,1-color))return false;
            }else if(colors[w]==colors[v]){
                return false;
            }
        }
        return true;
    }


    public static void main(String[] args) {
        UndirectedGraph graph = new UndirectedGraph("t.txt");
        System.out.println(graph);
        BiPartitionDetection graphDFS = new BiPartitionDetection(graph);
        System.out.println(graphDFS.biPart);
    }
}
